/*
 * LEN.h
 *
 *  Created on: May 13, 2012
 *      Author: dzm
 */

#ifndef LEN_H_
#define LEN_H_

#include "GateWay.h"
#include <cmath>
#include <QtAlgorithms>
#include <QVector>

struct DesNode{
	short* m;
};

class RecordNode{
public:

	short* m;
	bool isLocalDes;
	QVector<unsigned short> outport;

};


class LENAlgor{

public:

	void Stat(QVector<QVector<short> >& det,QVector<int>& most,QVector<DesNode> des){
		std::cout<<des.size()<<std::endl;

		for(int j=0; j< GateWay::dimension;j++){
			for(int i=0; i < des.size(); i++ ){

				if(det[i][j]==-1){
					//偶数装－1
					most[2*j]++;
				}else if(det[i][j]==1){
					//奇数装＋1
					most[2*j+1]++;
				}else{

				}
			}
		}
	}
	int LeastDim(int biggest,QVector<int>& most){
		for(int i = 0; i < most.size(); i++){
			if(most[i]==biggest){
				return i;
			}
		}
	}

	int Compare(QVector<QVector<short> >& det, QVector<int>& most, QVector<DesNode> des, bool& isDes){
		//如果本地就是目的地，记录一下
		isDes = false;
		for(int i = 0;i < des.size();i++){
			for(int j = 0;j < GateWay::dimension;j++){
				if(isDes==true){
					break;
				}
				if(det[i][j]!=0){
					isDes = false;
					break;
				}else if(j == (GateWay::dimension-1)){
					isDes = true;
				}
			}
		}

		//比较哪个维不同的目标节点最多
		QVector<int> tempmost(2*GateWay::dimension);
		qCopy(most.begin(), most.end(), tempmost.begin());
		qSort(tempmost.begin(), tempmost.end());
		if(tempmost[2*GateWay::dimension-1]==0){
			return 2*GateWay::dimension;
		}
//		return LeastDim(tempmost[2*GateWay::dimension],most);
		return most.indexOf(tempmost[2*GateWay::dimension-1]);
	}

	void AssembleDes(int l, QVector<QVector<short> >& det, QVector<DesNode>& nextDes, QVector<DesNode>& des){
		//求出维度
		int d = l / 2;          //d是存在偏差最多的纬度
		QVector<int> removeIndex;
		for(int i=0; i < des.size() ; i++ ){
			if(det[i][d]==2*(l%2)-1){        //看第i个目的地的d纬度的方向是不是和此时遍历的同方向，如果同方向则执行下面语句
				nextDes.push_back(des.at(i));//同方向则把目标节点i放入nextDes中
				removeIndex.push_back(i);    //然后在removeIndex上添加这个序号i
			}
		}

		//从组播目的点剔除由下一跳传送的点
		for(int i=0; i < removeIndex.size(); i++){
			//每次剔除一个后，des的编号会改变，需要通过－i调整
			des.remove(removeIndex[i]-i);
		}

	}

	void AddRecord(int l,int traverseTime,unsigned short inport,unsigned short outport,bool isDes,DesNode& current,QVector<DesNode> des,QVector<RecordNode>& RN,int localRecord, int& num_of_record,int & num_of_unicast, int & num_of_multicast,int& overlap){
		//添加目的地record
		if(l==2*GateWay::dimension ){
			if(traverseTime==0){
				num_of_record++;
				RN.resize(num_of_record);
				RN[num_of_record-1].isLocalDes=true;
				RN[num_of_record-1].m = new short[GateWay::dimension];
				for(int i=0;i<GateWay::dimension;i++){
					RN[num_of_record-1].m[i]=current.m[i];
				}
				RN[num_of_record-1].outport.push_back(2*GateWay::dimension);
			}
		}else if((outport+GateWay::dimension)%(2*GateWay::dimension)!=inport ||
				des.size()!=0 || traverseTime!=0){
			//添加组播的其他outport端口
			if(traverseTime!=0){
				RN[localRecord].outport.push_back(outport);
			}
			//添加纯单播拐点
			if(traverseTime==0 && des.isEmpty() && (!isDes)){
				num_of_unicast++;
				num_of_record++;
				RN.resize(num_of_record);
				RN[localRecord].isLocalDes=true;
				RN[localRecord].m = new short[GateWay::dimension];
				for(int i=0;i<GateWay::dimension;i++){
					RN[localRecord].m[i]=current.m[i];
				}
				RN[localRecord].outport.push_back(outport);
			}else if(traverseTime==0 && isDes){
				//添加组播（兼目的地）拐点
				num_of_multicast++;
				overlap++;
				num_of_record++;
				RN.resize(num_of_record);
				RN[localRecord].isLocalDes=true;
				RN[localRecord].m = new short[GateWay::dimension];
				for(int i=0;i<GateWay::dimension;i++){
					RN[localRecord].m[i]=current.m[i];
				}
				RN[localRecord].outport.push_back(2*GateWay::dimension);
				RN[localRecord].outport.push_back(outport);
			}else if(traverseTime==0 && (!des.isEmpty()) && (!isDes)){
				//添加纯组播拐点
				num_of_multicast++;
				num_of_record++;
				RN.resize(num_of_record);
				RN[localRecord].isLocalDes=false;
				RN[localRecord].m = new short[GateWay::dimension];
				for(int i=0;i<GateWay::dimension;i++){
					RN[localRecord].m[i]=current.m[i];
				}
				RN[localRecord].outport.push_back(outport);
			}
		}
	}


	void Traverse(unsigned short inport,DesNode& current, QVector<DesNode> des, QVector<RecordNode>& RN, int& num_of_record,int & num_of_unicast, int & num_of_multicast,int& overlap){
		int traverseTime = 0;
		bool isDes = false;
		int localRecord = num_of_record;  //本地变量，解决num_of_record迭代更改，反回到原节点时已变的问题

		while(des.size()!=0){
			//装向量的容器
			QVector<QVector<short> > det(des.size());
			for(int i = 0; i<des.size();i++){
//				det[i].resize(GateWay::dimension);
			}
			//装偏差个数的容器
			QVector<int> most(2*GateWay::dimension);
	/*
			for(int i = 0; i < 2*GateWay::dimension;i++){
				most.push_back(0);
			}
	*/
			qFill(most.begin(), most.end(), 0);

			for( int i = 0; i < des.size() ; i++ ){
				for(int j = 0; j < GateWay::dimension;j++){
					short d = 0;
					if(des[i].m[j]-current.m[j]==0){
						d = 0;
					}else{
						d = (des[i].m[j]-current.m[j])/abs(des[i].m[j]-current.m[j]);
					}
					det[i].push_back(d);

				}
			}
			//统计每一维的分离情况
			Stat(det,most,des);

			int l = Compare(det,most,des,isDes);

			if(l==2*GateWay::dimension){  //证明本地节点就是目标节点
				std::cout << "TraverseTime= "  << traverseTime << std::endl;
				AddRecord(l, traverseTime, inport, 0, isDes, current, des, RN, localRecord, num_of_record, num_of_unicast, num_of_multicast,overlap);
				return;
			}

			QVector<DesNode> nextDes;
			DesNode nextCur ;
			nextCur.m = new short[GateWay::dimension];  //把本地节点存到nextCur里面
			for(int i=0;i<GateWay::dimension;i++){
				nextCur.m[i]=current.m[i];
			}
			nextCur.m[l/2] = current.m[l/2]+2*(l%2)-1;  //生成下一跳的位置，如果是增长就坐标＋1，否则坐标－1

			AssembleDes(l,det,nextDes,des);

			int outport = l/2;
			if((2*(l%2)-1)==1){    //往高处传的话会执行
				outport = outport+GateWay::dimension;
			}
			std::cout<<"l="<<l<<std::endl;

			//条件1：outport+GateWay::dimension)%(2*GateWay::dimension)!=inport 说明这个包在此点是要发生拐弯的
			//条件2：des.size()!=0 说明这个方向转发完后，在这个点上还有其他方向要转发（包括本地）
			//条件3：traverseTime!=0 说明在这个方向转发之前，这个点已经转发过其他的方向了，也就是这个点是一个多播拐点
			//这三个条件任意满足一个，都应该要作记录
			if((outport+GateWay::dimension)%(2*GateWay::dimension)!=inport ||
					des.size()!=0 || traverseTime!=0){
				std::cout << "traverseTime= " << traverseTime << std::endl;
				AddRecord(l, traverseTime, inport, outport,isDes, current, des, RN, localRecord, num_of_record, num_of_unicast, num_of_multicast,overlap);
			}

			Traverse((outport+GateWay::dimension)%(2*GateWay::dimension), nextCur, nextDes, RN, num_of_record, num_of_unicast, num_of_multicast,overlap);
			traverseTime++;
		}

	}

};

#endif /* LEN_H_ */
